package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;

public class S27 {
    ArrayList<String> res = new ArrayList<>();
    StringBuilder builder = new StringBuilder();
    String s = builder.toString();

    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
            return res;
        }
        dfs1(str, 0, new boolean[str.length()]);
        return res;
    }

    public void dfs1(String str, int depth, boolean[] used) {
        if (str.length() == depth) {
            res.add(new String(builder));
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            if (!used[i]) {
                used[i] = true;
                builder.append(str.charAt(i));
                dfs1(str, depth + 1, used);
                //回退
                String replace = builder.toString().replace(String.valueOf(str.charAt(builder.length() - 1)), "");
                used[i] = false;

            }
        }
    }

    public static void main(String[] args) {
        S27 s27 = new S27();
        String a = "ab";
        s27.Permutation(a);

//        String a1 = "ab";
//        String b = a1.replace("b", "");
//        System.out.println(b);

    }
}
